package list;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class MinhaLinkedList<E> implements List<E> {

	int size;
	
	ElementoLista inicio;
	ElementoLista fim;

	protected class ElementoLista {
		Object valor;
		ElementoLista proximo;
		ElementoLista anterior;

		public ElementoLista(Object valor,
				MinhaLinkedList<E>.ElementoLista proximo,
				MinhaLinkedList<E>.ElementoLista anterior) {
			super();
			this.valor = valor;
			this.proximo = proximo;
			this.anterior = anterior;
		}

		public ElementoLista(E element) {
			this.valor = element;
			this.proximo = this.anterior = null;
		}
	}

	public MinhaLinkedList() {
		this.inicio = null;
		this.fim = null;
		this.size = 0;
	}

	public void addFirst(E elemento) {
		ElementoLista novo = new ElementoLista(elemento);

		if (this.inicio != null) {
			this.inicio.anterior = novo;
			novo.proximo = this.inicio;
			this.inicio = novo;
			this.size++;
		} else {
			add(elemento);
		}
	}

	public void addLast(E elemento) {
		ElementoLista novo = new ElementoLista(elemento);

		if (this.fim != null) {
			this.fim.proximo = novo;
			novo.anterior = this.fim;
			this.fim = novo;
			this.size++;
		} else {
			add(elemento);
		}
	}

	@Override
	public boolean add(E e) {
		if (this.inicio == null) {
			ElementoLista novo = new ElementoLista(e, null, null);
			this.inicio = novo;
			this.fim = novo;
		} else {
			ElementoLista novo = new ElementoLista(e);

			novo.anterior = this.fim;
			this.fim.proximo = novo;
			this.fim = novo;
		}

		this.size++;
		return true;
	}

	@Override
	public boolean remove(Object o) {
		ElementoLista atual = this.inicio;

		// Achar a posição
		while (atual != null) {
			if (atual.valor.equals(o)) {
				break;
			}

			atual = atual.proximo;
		}

		if (atual != null) {
			if (atual == inicio) {
				inicio = inicio.proximo;
				inicio.anterior = null;
			} else if (atual == fim) {
				fim = fim.anterior;
				fim.proximo = null;
			} else {
				ElementoLista anterior = atual.anterior;
				ElementoLista proximo = atual.proximo;

				// if (anterior != null) {
				anterior.proximo = proximo;
				// }

				// if (proximo != null) {
				proximo.anterior = anterior;
				// }

				atual.proximo = null;
				atual.anterior = null;
			}

			this.size--;
			return true;
		}

		return false;
	}

	@Override
	public E remove(int index) {
		validaIndice(index);

		ElementoLista atual = this.inicio;
		int posicao = 0;

		// Achar a posição
		while (atual != null && posicao < index) {
			atual = atual.proximo;
			posicao++;
		}

		if (atual == inicio && inicio == fim) {
			this.inicio = null;
			this.fim = null;
		} else if (atual == inicio) {
			inicio = inicio.proximo;
			inicio.anterior = null;
		} else if (atual == fim) {
			fim = fim.anterior;
			fim.proximo = null;
		} else {
			if (posicao == index) {
				ElementoLista anterior = atual.anterior;
				ElementoLista proximo = atual.proximo;

				if (anterior != null) {
					anterior.proximo = proximo;
				}

				if (proximo != null) {
					proximo.anterior = anterior;
				}

				atual.proximo = null;
				atual.anterior = null;
			}
		}

		E valor = (E) atual.valor;
		this.size--;

		return valor;
	}

	public E removeFirst() {
		if (this.inicio != null) {
			E valorInicio = (E) this.inicio.valor;

			if (this.inicio.proximo != null) {
				this.inicio.proximo.anterior = null;
				this.inicio = this.inicio.proximo;
			} else {
				this.inicio = null;
			}

			this.size--;
			return valorInicio;
		}

		return null;
	}

	public E removeLast() {
		if (this.fim != null) {
			E valorFim = (E) this.fim.valor;

			if (this.fim.anterior != null) {
				this.fim.anterior.proximo = null;
				this.fim = this.fim.anterior;
			} else {
				this.fim = null;
			}

			this.size--;
			return valorFim;
		}

		return null;
	}

	@Override
	public E get(int index) {
		validaIndice(index);

		ElementoLista atual = this.inicio;

		int i = 0;
		while (i < index) {
			atual = atual.proximo;
			i++;
		}

		return (E) atual.valor;
	}

	public E getFirst() {
		if (this.inicio != null) {
			return (E) this.inicio.valor;
		}

		return null;
	}

	public E getLast() {
		if (this.fim != null) {
			return (E) this.fim.valor;
		}

		return null;
	}

	private void validaIndice(int index) {
		if (index > this.size - 1) {
			throw new ArrayIndexOutOfBoundsException();
		}
	}

	@Override
	public E set(int index, E element) {
		validaIndice(index);

		ElementoLista atual = this.inicio;
		int posicao = 0;

		// Achar a posição
		while (atual != null && posicao < index) {
			atual = atual.proximo;
			posicao++;
		}

		if (posicao == index) {
			ElementoLista novo = new ElementoLista(element);
			ElementoLista anterior = atual.anterior;
			ElementoLista proximo = atual.proximo;

			anterior.proximo = novo;
			novo.anterior = anterior;

			proximo.anterior = novo;
			novo.proximo = proximo;

		}

		return (E) atual.valor;
	}

	@Override
	public void add(int index, E element) {
		validaIndice(index);

		ElementoLista atual = this.inicio;
		int posicao = 0;

		// Achar a posição
		while (atual != null && posicao < index) {
			atual = atual.proximo;
			posicao++;
		}

		if (posicao == index) {
			ElementoLista novo = new ElementoLista(element);
			ElementoLista anterior = atual.anterior;

			anterior.proximo = novo;
			novo.anterior = anterior;

			novo.proximo = atual;
			atual.anterior = novo;

			this.size++;
		}
	}

	@Override
	public int indexOf(Object o) {
		ElementoLista atual = this.inicio;
		int posicao = 0;

		// Achar a posição
		while (atual != null) {
			if (atual.valor.equals(o)) {
				return posicao;
			}

			atual = atual.proximo;
			posicao++;
		}

		return -1;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return this.size == 0;
	}

	@Override
	public boolean contains(Object o) {
		ElementoLista atual = this.inicio;

		while (atual != null) {
			if (atual.valor.equals(o)) {
				return true;
			}
			atual = atual.proximo;
		}

		return false;
	}

	@Override
	public Iterator<E> iterator() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		for (Object object : c) {
			if (!contains(object)) {
				return false;
			}
		}

		return true;
	}

	@Override
	public boolean addAll(Collection<? extends E> c) {
		ElementoLista atual = this.fim;

		if (atual != null) {
			for (E e : c) {
				ElementoLista novo = new ElementoLista(e);
				atual.proximo = novo;
				novo.anterior = atual;
				novo.proximo = null;
				atual = novo;
			}
		}

		return c.size() > 0;
	}

	@Override
	public boolean addAll(int index, Collection<? extends E> c) {
		ElementoLista atual = this.inicio;
		int posicao = 0;

		while (atual != null && posicao > index) {
			atual = atual.proximo;
			posicao++;
		}

		if (posicao == index) {
			for (E e : c) {
				ElementoLista novo = new ElementoLista(e);
				ElementoLista anterior = atual.anterior;
				ElementoLista proximo = atual.proximo;

				anterior.proximo = novo;
				novo.anterior = anterior;

				proximo.anterior = novo;
				novo.proximo = proximo;

				atual = novo;
			}

			return true;
		}

		return false;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		for (Object object : c) {
			remove(object);
		}

		return c.size() > 0;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public void clear() {
		ElementoLista atual = this.inicio;

		while (atual != null) {
			ElementoLista proximo = atual.proximo;

			atual.anterior = null;
			atual.proximo = null;
			atual.valor = null;
			atual = proximo;
		}

		this.inicio = null;
		this.fim = null;
		this.size = 0;
	}

	@Override
	public int lastIndexOf(Object o) {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public ListIterator<E> listIterator() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public ListIterator<E> listIterator(int index) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public List<E> subList(int fromIndex, int toIndex) {
		// TODO Auto-generated method stub
		return null;
	}

}
